package java_0306_MapAndSet;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class HeapSort {

    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {//比较的趟数
            boolean isSwaped=false;
            for (int j = 0; j < arr.length-i-1; j++) {//循环进行元素的比较交换//-1是因为防止越界
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    isSwaped=true;
                }
            }
            if(!isSwaped){
                break;
            }
        }
    }

    //传入一个数组，对其进行堆排序
    public static void heapSort(int[] arr){
        //1.先将arr进行heapify操作调整为最大堆
        //heapify:从最后一个非叶子节点【即最后一个叶子节点的父节点=（最后一个叶子节点索引-1）/2】开始进行siftDown操作
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            siftDown(arr,i,arr.length);////传入arr,下沉的位置的索引，数组长度
        }
        //2.此时arr就被调整为一个最大堆了,再次遍历最大堆
        //交换堆顶与最后一个元素值，再对除最后一个元素以外作为一个堆进行堆顶元素下沉操作
        for (int i = arr.length-1; i > 0; i--) {
            swap(arr,0,i);
            siftDown(arr,0, i);
        }
    }
    private static void siftDown(int[] arr, int i, int length) {
       //当有左右孩子才能下沉，下沉到当前值大于左右孩子值下沉结束
        while((2*i+1)<length){//为啥不是2*i+2:有的节点没有右孩子
            //判断是否有右孩子
            int j=(i<<1)+1;
            if(j+1<length&&arr[j]<arr[j+1]){
                j=j+1;
            }
            //此时j为左右孩子较大的那个的索引
            if(arr[i]>arr[j]){
                //元素下沉结束
                break;
            }else{
                //交换i索引位置的值和j索引位置的值
                swap(arr,i,j);
                //继续向后进行元素下沉判断
                i=j;
            }
        }

    }
    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public static void main(String[] args) {
        int n=100000;
        int[] arr=new int[n];
        //生成随机数
        ThreadLocalRandom random=ThreadLocalRandom.current();
        for (int i = 0; i < n; i++) {
            arr[i]=random.nextInt(0,Integer.MAX_VALUE);
        }
        int[] arr1=Arrays.copyOf(arr,n);//拷贝一份arr
        //对arr做冒泡排序，对arr1做堆排序
        Long start=System.nanoTime();//当前系统时间
        bubbleSort(arr);
        Long end=System.nanoTime();//再次获取当前时间（nanoTime获取的是纳秒）
        if(isSorted(arr)){
            System.out.println("冒泡排序共耗时："+(end-start)/1000000+"ms");
        }
        start=System.nanoTime();
        heapSort(arr1);
        end=System.nanoTime();
        if(isSorted(arr1)){
            System.out.println("堆排序共耗时："+(end-start)/1000000+"ms");
        }
    }
    //排序是否正确
    private static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]){
                System.out.println("sort error");
                return false;
            }
        }
        return true;
    }
}
